package demo4;

import lombok.Getter;
import lombok.Setter;

import java.util.ArrayList;
import java.util.Random;

public class CustomTree {
    public NodeForTree createNodeForTree(int data){
        return new NodeForTree(data);
    }
    @Getter
    @Setter
    public class NodeForTree{
        private int data;
        private int size=1;
        private NodeForTree left ;
        private NodeForTree right ;
        private NodeForTree parent;
        public NodeForTree(){}
        public NodeForTree(int data){this.data=data;}
        // arrays 0,7
        /**
         0,1,2,3,4,5,6
         */
        public NodeForTree fromArraysToNode(int[] arrays,int low,int high){
            if(low>high){
                return null;
            }
            int center = ( low + high )/2;
            NodeForTree nodeForTree = new NodeForTree(arrays[center]);
            nodeForTree.left=fromArraysToNode(arrays,low,center-1);
            nodeForTree.right=fromArraysToNode(arrays,center+1,high);

            return nodeForTree;
        }
    /**
     0 , 1 , 2

     */
    // todo rebalance
        public void insert(int data){

            if(this.data>data){
                if(this.left==null){
                    this.left=new NodeForTree(data);
                    this.left.parent=this;
                }else{
                    this.left.insert(data);
                }
            }else if(this.data<=data){
                if(this.right==null){
                    this.right=new NodeForTree(data);
                    this.right.parent=this;
                }else{
                    this.right.insert(data);
                }
            }
            // when size = 1 ;
            this.size++;
        }
        /**
         delete association.
         */
        public void delete(int data,NodeForTree root){
            NodeForTree nodeForTree = find(data, root);
            settingNullForNode(nodeForTree);
            if(nodeForTree.left ==null && nodeForTree.right==null){
            }else{
                ArrayList<Integer> integers = new ArrayList<>();
                inOrderTraversal(nodeForTree,integers);
                for (Integer integer : integers) {
                    // todo rebalance when insert order is [0,1,2,3..]
                    root.insert(integer);
                }
            }

        }

        private void settingNullForNode(NodeForTree nodeForTree){
            boolean isLeft = nodeForTree.parent.left==nodeForTree;
            if(isLeft){
                nodeForTree.parent.left=null;
            }else{
                nodeForTree.parent.right=null;
            }
        }
        public void  inOrderTraversal(NodeForTree node){
            if(node!=null){
                inOrderTraversal(node.left);
                visit(node);
                inOrderTraversal(node.right);
            }
        }
        private void visit(NodeForTree node){
            System.out.println(" the data  of current node is:"+node.data);
        }
        public void  inOrderTraversal(NodeForTree node, ArrayList<Integer> list){
            if(node!=null){
                inOrderTraversal(node.left,list);
                list.add(node.data);
                inOrderTraversal(node.right,list);
            }
        }
        /**
         from the root node find,
            0,1,2,3,4,5,6
         */
        public NodeForTree find(int data,NodeForTree node){
            if(node==null)return null;

            if(data<node.data){
                return find(data,node.left);
            }else if(data>node.data){
                return find(data,node.right);
            }else{
                return node;
            }

        }
        /**
         */
        public NodeForTree getRandomNode(){
            int leftSize = this.left!=null?this.left.size:0;
            Random random = new Random();
            // size =3 , index[0,2]
            int index = random.nextInt(size);// size=10 , index=[0,9]  left:[0,1) median:[1] rigt:[2,9]
            if(leftSize==index){//1 =index
                return this;
            }else if(index<leftSize){ // 1>index(0)
                return this.left.getRandomNode();
            }else{
                return this.right.getRandomNode();
            }
        }
    }
}
